package com.hellohu.dp;

import java.util.ArrayList;
import java.util.List;

import org.assertj.core.api.Assertions;
import org.junit.Test;

public class OneZeroPackage {

    @Test
    public void test() {
        Assertions.assertThat(violenceSolution(new int[] { 2, 2, 4, 6, 3 }, 9, 0, 9)).isEqualTo(9);
        Assertions.assertThat(divideSolution(new int[] { 2, 2, 4, 6, 3 }, 9, 4)).isEqualTo(9);
        Assertions.assertThat(memoSolution(new int[] { 2, 2, 4, 6, 3 }, 9, 4, new int[5][10])).isEqualTo(9);
        Assertions.assertThat(dynamicProgrammingSolution(new int[] { 2, 2, 4, 6, 3 }, 9)).isEqualTo(9);
    }

    /**
     * 暴力解决
     * 
     * @param weight   物品重量数组
     * @param capacity 容量
     * @param i        剩余i以后物品
     * @param w        背包目前的重量
     * @return
     */
    public int violenceSolution(int[] weight, int capacity, int i, int w) {
        // 物品考察完毕或背包已经装满了
        if (i >= weight.length || capacity == w) {
            return w;
        }
        // ->
        // weight[i] <= capacity - w -> f(i+1,w+weight[i]),f(i+1,w)
        // 否则 f(i+1,w)
        if (weight[i] <= capacity - w) {
            // 能装下，有两种选择，装，或不装
            return Math.max(violenceSolution(weight, capacity, i + 1, w + weight[i]),
                    violenceSolution(weight, capacity, i + 1, w));
        } else {
            // 装不下
            return violenceSolution(weight, capacity, i + 1, w);
        }
    }

    /**
     * 分治的解决方案
     * 
     * @param weight   物品重量
     * @param capacity 容量
     * @param i        到了第i个决策（包括0）
     * @return
     */
    public int divideSolution(int[] weight, int capacity, int i) {
        if (capacity == 0 || i == 0) {
            return 0;
        }
        // f(i,c) = weight[i] <= capacity ? max(f(i-1,c-w[i]),f(i-1,j)+w[i]) : f(i-1,j);
        if (weight[i] <= capacity) {
            // 剩余容量能装下，有两种选择，装，或不装
            return Math.max(divideSolution(weight, capacity - weight[i], i - 1) + weight[i],
                    divideSolution(weight, capacity, i - 1));
        } else {
            // 否则只能不装
            return divideSolution(weight, capacity, i - 1);
        }
    }

    /**
     * 备忘录方法解决问题
     * 
     * @param weight
     * @param capacity
     * @param i
     * @param memo
     * @return
     */
    public int memoSolution(int[] weight, int capacity, int i, int[][] memo) {
        if (capacity == 0 || i == 0) {
            return 0;
        }
        if (memo[i][capacity] > 0) {
            return memo[i][capacity];
        }
        // f(i,c) = weight[i] <= capacity ? max(f(i-1,c-w[i]),f(i-1,j)+w[i]) : f(i-1,j);
        if (weight[i] <= capacity) {
            // 剩余容量能装下，有两种选择，装，或不装
            memo[i][capacity] = Math.max(divideSolution(weight, capacity - weight[i], i - 1) + weight[i],
                    divideSolution(weight, capacity, i - 1));
        } else {
            // 否则只能不装
            memo[i][capacity] = divideSolution(weight, capacity, i - 1);
        }
        return memo[i][capacity];
    }

    /**
     * 动态规划解决问题
     * 
     * @param w
     * @param c
     * @return
     */
    public int dynamicProgrammingSolution(int[] w, int c) {
        // dp[i][j] 前i个物品，容量为j的，01背包最大值
        int[][] dp = new int[w.length + 1][c + 1];
        // Arrays.fill(dp, 0);
        for (int i = 1; i <= w.length; ++i) {
            for (int j = 1; j <= c; ++j) {
                if (w[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j - w[i - 1]] + w[i - 1], dp[i - 1][j]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        List<List<Pair>> outputSolutions = getAllSolutions(dp, w, w.length, c, new ArrayList<>(), new ArrayList<>());
        System.out.println(outputSolutions);
        return dp[w.length][c];
    }

    private class Pair {

        public Pair(int i, int w) {
            super();
            this.i = i;
            this.w = w;
        }

        int i;
        int w;

        @Override
        public String toString() {
            return "{i=" + i + ", w=" + w + "}";
        }

    }

    /**
     * 获取所有解决方案
     * 
     * @param dp
     * @return
     */
    public List<List<Pair>> getAllSolutions(int[][] dp, int[] w, int i, int j, List<Pair> cur,
            List<List<Pair>> result) {
        if (i == 0 || j == 0) {
            result.add(cur);
            return result;
        }
        List<Pair> clone = null;
        if (w[i - 1] <= j) {
            if (dp[i][j] == dp[i - 1][j]) {
                clone = new ArrayList<>(cur);
                getAllSolutions(dp, w, i - 1, j, cur, result);
            }
            if (dp[i][j] == dp[i][j - w[i - 1]] + w[i - 1]) {
                if (clone == null) {
                    clone = cur;
                }
                clone.add(new Pair(i, w[i - 1]));
                getAllSolutions(dp, w, i - 1, j - w[i - 1], clone, result);
            }
        } else {
            getAllSolutions(dp, w, i - 1, j, cur, result);
        }
        return result;
    }
}
